package 搜索.DFS;
/*
解题思路：
    这题求岛屿最大面积，又要求岛屿要连续，其实就是可达性问题很明显要用DFS。

    知道要用DFS了就去套DFS模板，具体细节看代码注释
 */
public class 岛屿的最大面积_695 {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int res = 0;//用来保存结果
        for (int r = 0; r < grid.length; r++) {//遍历每一行
            for (int c = 0; c < grid[0].length; c++) {//遍历每一列
                if (grid[r][c] == 1) {//只有发现了岛屿才开始扩展搜索，如果岛屿都没有发现，那就没有展开的必要
                    int area = DFS(grid, r, c);
                    res = Math.max(res, area);//对于本次循环来说res保存的是之前循环找到的最大岛屿数量，area是这一次找到的岛屿数量，  比较二者将最大的赋值给res，可以保证res一直是最大岛屿数量
                }
            }

        }
        return res;
    }

    public int DFS(int[][] grid, int r, int c) {
        if (!(0 <= r && r < grid.length
                && 0 <= c && c < grid[0].length)) {//超出了边缘，走不下去了
            return 0;
        }

        if (grid[r][c] != 1) {//不是岛屿也返回，因为岛屿要相连的1，一旦出现0就要返回
            return 0;
        }

        grid[r][c] = 0;//经过前面两个if筛选。可以确保正在遍历的这个值是岛屿（1），遍历过后为了避免再次遍历，就将它变成0，简称“沉岛”。【还可以建一个集合Visited用来保存遍历过的岛屿，但是这题没有要求不能修改原数组，为了节省空间我们就直接修改原数组为0】

        int area = 1;//正在遍历的值为1，是岛屿，所以岛屿面积至少为1.

        area += DFS(grid, r - 1, c);//向上遍历
        area += DFS(grid, r + 1, c);//向下遍历
        area += DFS(grid, r, c - 1);//向左遍历
        area += DFS(grid, r, c + 1);//向右遍历

        //上面四句area+=xxX;相当于把上下左右四个方向的岛屿数量全加起来了。
        return area;
    }
}
